package com.zy.sort;

import java.util.List;
import java.util.Optional;

/**
 * @Author zhaoyi
 * @date 2020/4/1
 * TopK的实现
 */
public class TopK<T extends Comparable<? super T>> {

    public T getTopK(List<T> list, int k) {
        return Optional.ofNullable(list)
                .filter(f -> f.size() > k)
                .map((List<T> r) -> {
                    //进行逻辑处理topK
                    return top(r, k - 1, 0, r.size() - 1);
                }).orElseGet(null);
    }


    private T top(List<T> list, int k, int left, int right) {
        int point = findPoint(list, left, right);
        if (point == k) {
            return list.get(point);
        } else if (point < k) {
            return top(list, k, point + 1, right);
        } else {
            return top(list, k, left, point - 1);
        }
    }


    //倒序
    private int findPoint(List<T> list, int left, int right) {
        //设定基准值（pivot）
        int point = right;
        --right;
        boolean flagRight = false;
        boolean flagLeft = false;

        //只能等于时退出
        while (right > left) {
            //还没找到右边大的
            if (!flagRight) {
                if (list.get(right).compareTo(list.get(point)) > 0) {
                    flagRight = true;
                } else {
                    --right;
                }

            }
            //还没找到 左边小的
            if (!flagLeft) {
                if (list.get(left).compareTo(list.get(point)) < 0) {
                    flagLeft = true;
                } else if (right > left) {
                    //防止上面移动后条件变化
                    ++left;
                }

            }
            if (flagRight && flagLeft) {
                swap(list, left, right);
                flagRight = false;
                flagLeft = false;
                --right;
                if (right > left) {
                    //防止上面移动后条件变化
                    ++left;
                }
            }
        }

        if (flagRight || list.get(right).compareTo(list.get(point)) > 0) {
            //说明最终这个值大于 point 的
            swap(list, point, right + 1);
            return right + 1;
        } else if (flagLeft || list.get(right).compareTo(list.get(point)) < 0) {
            //说明最终这个值 小于 point 的
            swap(list, point, left);
            return left;
        }
        return right;
    }

    private void swap(List<T> list, int i, int j) {
        T t = list.get(i);
        list.set(i, list.get(j));
        list.set(j, t);
    }


}
